package Solution.problem069;

/**
 * @program Leetcode
 * @description:
 *
 * The square root of 8 is 2.82842..., and since
 *              the decimal part is truncated, 2 is returned.
 *  根据题干只求出平方根的整数部分，所以如果num的平方小于x,num+1的平方大于x的话，num就是所求的值，
 *  这个题有点类似查找中间数，可以采用二分查找
 * @author: lishangsheng
 * @create: 2019/06/09 21:24
 */
public class Solution {
    public static int mySqrt(int x) {
        if(x==0){
            return x;
        }
        return (int) getTheNum(1,x,x);

    }

    private static long getTheNum(long start,long end,int x){
        long sum=start+end;
        long mid=(sum)/2;
        long result = 0;
        long product=mid*mid;
        if(product > x || product < 0){
            result= getTheNum(start,mid,x);
        }else if(product<=x){
            long biggerProduct=(mid+1)*(mid+1);
            if(biggerProduct>x){
                result= mid;
            }else {
                result=getTheNum(mid,end,x);
            }
        }
        return result;
    }

    public static void main(String[] args){
        int result=mySqrt(2147395599);
        System.out.println(result);
/*
        int result2=mySqrt(8);
        System.out.println(result2);

        int result3=mySqrt(9);
        System.out.println(result3);*/
    }
}
